package fun.ticsmyc.question.dp;

import java.util.Arrays;

/**
 * \1691. 堆叠长方体的最大高度
 * \354. 俄罗斯套娃信封问题
 */
public class 套娃问题 {

    public int maxHeight(int[][] cuboids) {
        for (int[] cuboid : cuboids) {
            Arrays.sort(cuboid);
        }
        Arrays.sort(cuboids, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int[] dp = new int[cuboids.length];
        int res = 0;
        for (int i = 0; i < cuboids.length; ++i) {
            dp[i] = cuboids[i][2];
            res = Math.max(res, dp[i]);
        }
        for (int i = 1; i < cuboids.length; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (cuboids[i][1] >= cuboids[j][1] && cuboids[i][2] >= cuboids[j][2]) {
                    dp[i] = Math.max(dp[i], dp[j] + cuboids[i][2]);
                    res = Math.max(res, dp[i]);
                }
            }
        }
        return res;

    }
}
